Міністерство освіти і науки України Національний університет «Львівська Політехніка» Інститут комп’ютерних технологій автоматики та метрології Кафедра Безпеки Інформаційних Технологій
Звіт Про виконання лабораторної роботи № 5 “Криптографічні системи та протоколи”  Львів 2012 Мета роботи: Вивчити математичні основи побудови алгоритму шифрування RSA, методи криптоаналізу та вимоги до стійкості алгоритму RSA, навчитися розробляти програмне забезпечення для шифрування та цифрового підпису з використанням алгоритму RSA. Теоретичні відомості Безпека RSA базується на складності розкладу на множники великих чисел. Відкритий та закритий ключі є функціями двох великих (більше двохсот десяткових розрядів) простих чисел. Відновлення відкритого тексту за шифротекстом і відкритим ключем еквівалентне розкладу на множники двох великих чисел. Для генерації двох ключів використовуються два великих випадкових простих числа p і q однакової довжини. Розширений алгоритм Евкліда використовується для обчислення ключа розшифрування d такого, що ed=1(mod(p-1)(q-1)). (1) Іншими словами d=e-1mod((p-1)(q-1)) (2) d і n=pq є взаємно простими числами. Числа e і n – це відкритий ключ, а число d – закритий. Для шифрування повідомлення m воно спочатку розбивається на цифрові блоки, які менші за n (для двійкових даних вибирається найбільший степінь числа 2, менший за n). А саме, якщо p і q – 100-розрядні прості числа, то n буде мати приблизно 200 розрядів і кожен блок повідомлення mi повинен мати також приблизно 200 розрядів. Зашифроване повідомлення c буде складатися з блоків ci такої ж довжини. Формула шифрування має вигляд: ci=mie mod n (3) Для розшифрування повідомлення береться кожен зашифрований блок ci і обчислюється mi=cid mod n (4) Оскільки cid=(mie)d=mied=mik(p-1)(q-1)+1=mimik(p-1)(q-1)=mi*1=mi то формула відновлює повідомлення. Для піднесення до степеня за модулем n використовується бінарний алгоритм: Задано:
. Обчислити:
. Вважається, що d < n. Алгоритм у вигляді прямолінійної програми для обчислення функції
має вигляд. Показник
подається у двійковій системі числення:
, де
і
. Присвоюється
. Тоді
-та команда задається так:
Всього команд
. Результатом виконання останньої є
Всього витрачається
множень. Нехай p=47, q=71. Тоді N=pq=3337. Ключ e не повинен мати спільних множників (p-1)(q-1)=46*70=3220 Вибираємо випадково e, наприклад, 79. Тоді d=79-1mod 3220=1019. Під час обчислення використаний розширений алгоритм Евкліда. Зробимо e і n загальнодоступними, а d збережемо в секреті. Відкидаємо p і q. Для шифрування повідомлення m=6882326879666683 спочатку розбиваємо його на малі блоки. Для розглянутого випадку використовуємо трибуквенні блоки. Повідомлення розіб’ється на шість блоків mi. m1=688 m2=232 m3=687 m4=966 m5=668 m6=003 Перший блок шифрується 68879 mod 3337=1570=c1. Виконуючи такі самі операції для наступних бітів, одержимо шифротекст повідомлення: c=1570 2756 2091 2276 2423 158 Для розшифрування потрібно виконати операцію піднесення до степеня, використовуючи ключ розшифрування 1019: 15701019 mod 3337 =688 =m1 Аналогічно відновлюється інша частина повідомлення. ЗАВДАННЯ 1) Вивчити математичні основи, принципи побудови та вразливості алгоритму шифрування RSA. 2) Скласти блок-схеми алгоритмів та програму для реалізації шифрування та розшифрування відкритого тексту за допомогою алгоритму шифрування RSA. Забезпечити введення ключів з клавіатури. Для виконання операції піднесення до степеня за модулем використати бінарний алгоритм. Блок-схема: Остаточна версія програми: outtext.setText(null); if (code.isSelected() == true) { String intexts = this.intext.getText(); StringBuilder sb = new StringBuilder(intexts); for (;;) { if (sb.length() % 3 != 0) { sb.append(0); } else { break; } } String inter = sb.toString(); char textchd...